In mathematics, discrepancy theory describes the deviation of a situation from the state one would like it to be in. It is also called the theory of irregularities of distribution. This refers to the theme of ''classical'' discrepancy theory, namely distributing points in some space such that they are evenly distributed with respect to some (mostly geometrically defined) subsets. The discrepancy (irregularity) measures how far a given distribution deviates from an ideal one.
Discrepancy theory can be described as the study of inevitable irregularities of distributions, in
measure-theoretic and
combinatorial
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many app ...
settings. Just as
Ramsey theory
Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in Ramsey theory typically ask a ...
elucidates the impossibility of total disorder, discrepancy theory studies the deviations from total uniformity.
A significant event in the history of discrepancy theory was the 1916 paper of
Weyl
Hermann Klaus Hugo Weyl, (; 9 November 1885 – 8 December 1955) was a German mathematician, theoretical physicist and philosopher. Although much of his working life was spent in Zürich, Switzerland, and then Princeton, New Jersey, he is ass ...
on the uniform distribution of sequences in the unit interval.
__NOTOC__
Theorems
Discrepancy theory is based on the following classic theorems:
* The theorem of
van Aardenne–Ehrenfest
* Axis-parallel rectangles in the plane (
Roth Roth may refer to:
Places
Germany
* Roth (district), in Bavaria, Germany
** Roth, Bavaria, capital of that district
** Roth (electoral district), a federal electoral district
* Rhineland-Palatinate, Germany:
** Roth an der Our, in the district B ...
, Schmidt)
* Discrepancy of half-planes (Alexander,
Matoušek)
* Arithmetic progressions (Roth, Sarkozy,
Beck
Beck David Hansen (born Bek David Campbell; July 8, 1970) is an American musician, singer, songwriter, and record producer. He rose to fame in the early 1990s with his Experimental music, experimental and Lo-fi music, lo-fi style, and became ...
, Matousek &
Spencer)
*
Beck–Fiala theorem
In mathematics, the Beck–Fiala theorem is a major theorem in discrepancy theory due to József Beck
József Beck (Budapest, Hungary, February 14, 1952) is a Harold H. Martin Professor of Mathematics at Rutgers University.
His contributions to ...
* Six Standard Deviations Suffice (Spencer)
Major open problems
The unsolved problems relating to discrepancy theory include:
* Axis-parallel rectangles in dimensions three and higher (folklore)
*
Komlós conjecture
*
Heilbronn triangle problem
In discrete geometry and discrepancy theory, the Heilbronn triangle problem is a problem of placing points in the plane, avoiding triangles of small area. It is named after Hans Heilbronn, who conjectured that, no matter how points are placed ...
on the minimum area of a triangle determined by three points from an ''n''-point set
Applications
Applications for discrepancy theory include:
* Numerical integration:
Monte Carlo method
Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be determi ...
s in high dimensions.
* Computational geometry:
Divide-and-conquer algorithm
In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved dire ...
.
* Image processing:
Halftoning
Halftone is the reprographic technique that simulates continuous-tone imagery through the use of dots, varying either in size or in spacing, thus generating a gradient-like effect.Campbell, Alastair. The Designer's Lexicon. ©2000 Chronicle, S ...
* Random trial formulation:
Randomized controlled trial
A randomized controlled trial (or randomized control trial; RCT) is a form of scientific experiment used to control factors not under direct experimental control. Examples of RCTs are clinical trials that compare the effects of drugs, surgical te ...
See also
*
Discrepancy of hypergraphs Discrepancy of hypergraphs is an area of discrepancy theory.
Definitions
In the classical setting, we aim at partitioning the vertices of a hypergraph \mathcal=(V, \mathcal) into two classes in such a way that ideally each hyperedge contains th ...
References
Further reading
*
*
*
{{Authority control
Diophantine approximation
Unsolved problems in mathematics
Discrepancy theory
Measure theory